The edit distance problem is to find the minimum cost of edit operations to transform one string to the other. Myers presented an algorithm for edit distance problem with with that the cost of an insertion or deletion is 1 and the cost of a replacement is 2. The computation procedure is to calculate the furthest contour of distance 0, the furthest contour of distance 1, then distance 2, and so on. This algorithm performs well when the two strings are similar.
int Myers_Alg(char *A, char *B, int m, int n)
{
//D=j-i
int *realV = new int[2*(m+n)];
int *V, i, j, D = 0;
V = realV + m + n;
memset(realV, -1, (2*(m+n))*sizeof(int));
V[1] = 0;
for(D = 0; D <= m+n; D++){
for(int k =- D;k <= D;k += 2){
if(k == -D || (k != D && V[k-1] < V[k+1])){
j=V[k+1];
}
else{
j=V[k-1]+1;
}
i = j-k;
while(j < n && i < m && B[j+1] == A[i+1]){
i++;
j++;
}
V[k] = j;
if(j >= n && i >= m){
delete [] realV;
return D;
}
}
}
}